#include <bits/stdc++.h>
using namespace std;
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

typedef long long LL;

const int N = 1e3+5, M = 1e4+5;

int h, n, a[N], b[N];
int dp[M];

inline void update(int &a, int b)
{
    if (b == -1) return;
    if (a > b || a == -1) a = b;
}

int main(int argc, char const *argv[])
{
    cin >> h >> n;
    for (int i=1; i<=n; ++i) cin >> a[i] >> b[i];
    memset(dp, -1, sizeof dp);
    dp[h] = 0;
    for (int i=0; i<n; ++i)
    for (int j=h; j>=0; --j)
    {
        if (!~dp[j]) continue;
        update(dp[max(j-a[i+1], 0)], dp[j] + b[i+1]);
    }
    // dbg(dp[1][1]);
    printf("%d\n", dp[0]);
    return 0;
}
